#include <Types.h>
#include <DedupMem.h>
#include <BasicDagLibrary.h>
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
using namespace std;
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
template < typename node_t > DedupMem< node_t >::DedupMem( const U32 _deg ) : deg( _deg ) {
   // create zero node
   ZeroNode( zeroNode );

   // initialize with zero node
   #ifdef __USE_BIMAP__
   ddmMap.insert( typename bimap< node_t, U32 >::value_type( zeroNode, 0 ) );
   #else
   bakMap[ 0 ] = zeroNode;
   fwdMap[ zeroNode ] = 0;
   #endif
   refCow[ 0 ] = 0;
   
   for( U32 i = 0; i < maxPathLen; i++ ) {
      virtNodes[ i ] = 0;
      vpceNodes[ i ] = 0;
      // -- overcounts the uniqe path expanded nodes -- upcxNodes[ i ] = 0;
      uniqNodes[ i ] = 0;
   }
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
template < typename node_t > void DedupMem< node_t >::TransferStats( DagStatistics & dagStats, const U32 hgt ) {
   
   assert( hgt < maxPathLen );
   assert( dagStats.virtNodes.size() == 0 );
   assert( dagStats.vpceNodes.size() == 0 );
   // -- overcounts the uniqe path expanded nodes -- assert( dagStats.upcxNodes.size() == 0 );
   assert( dagStats.uniqNodes.size() == 0 );
   
   for( U32 i = 0; i < hgt+1; i++ ) {
      
      dagStats.virtNodes.push_back( virtNodes[i] );
      dagStats.vpceNodes.push_back( vpceNodes[i] );
      // -- overcounts the uniqe path expanded nodes -- dagStats.upcxNodes.push_back( upcxNodes[i] );
      dagStats.uniqNodes.push_back( uniqNodes[i] );
      
      virtNodes[ i ] = 0;
      vpceNodes[ i ] = 0;
      // -- overcounts the uniqe path expanded nodes -- upcxNodes[ i ] = 0;
      uniqNodes[ i ] = 0;
   }
   
   assert( virtNodes[ hgt+1 ] == 0 );
   assert( vpceNodes[ hgt+1 ] == 0 );
   // -- overcounts the uniqe path expanded nodes -- assert( upcxNodes[ hgt+1 ] == 0 );
   assert( uniqNodes[ hgt+1 ] == 0 );
}
template < typename node_t > void DedupMem< node_t >::SerializeNodes( vector< node_t > & nodes ) const {
   
   assert( nodes.size() == 0 );

   #ifdef __USE_BIMAP__
   #ifdef __USE_USO__
   typename bimap< bimaps::unordered_set_of< node_t >, bimaps::unordered_set_of< U32 > >::right_const_iterator it;
   #else
   typename bimap< node_t, U32 >::right_const_iterator it;
   #endif

   nodes.resize( ddmMap.left.size() );

   for( it = ddmMap.right.begin(); it != ddmMap.right.end(); it++ ) {
      nodes[ it->first/deg ] = it->second;
   }
   #else
   
   #ifdef __USE_USO__
   typename unordered_map< U32, node_t >::const_iterator it;
   #else
   typename map< U32, node_t >::const_iterator it;
   #endif

   nodes.resize( bakMap.size() );
   for( it = bakMap.begin(); it != bakMap.end(); it++ ) {
      nodes[ it->first/deg ] = it->second;
   }
   #endif
}
template < typename node_t > void DedupMem< node_t >::Audit( void ) const {
   assert( freeList.size() == 0 );
}
template < typename node_t > void DedupMem< node_t >::DecRC   ( const node_t & node ) {
   if( node == zeroNode ) { return; }
   #ifdef __USE_BIMAP__
   const U32 plid = ddmMap.left.find( node )->second;
   #else
   const U32 plid = fwdMap.find( node )->second;
   #endif
   //cout << "DecRC(): plid = " << plid  << endl;
   if( plid == 0 ) { return; }
   //cout << "DecRC()" << endl;
   refCow[ plid ] -= 1;
   if( refCow[ plid ] == 0 ) {
      // dealloc
      DeAlloc( node, plid );
   }      
}
template < typename node_t > U32  DedupMem< node_t >::Alloc   ( const node_t & node ) {
   // alloc
   #ifdef __USE_BIMAP__
   U32 newNodeIdx = deg*ddmMap.size();
   #else
   U32 newNodeIdx = deg*fwdMap.size();
   #endif
   if( freeList.size() ) {
      newNodeIdx = freeList.back();
      freeList.pop_back();
   }
   #ifdef __USE_BIMAP__
   ddmMap.insert( typename bimap< node_t, U32 >::value_type( node, newNodeIdx ) );
   #else
   fwdMap[ node ] = newNodeIdx;
   bakMap[ newNodeIdx ] = node;
   #endif
   refCow[ newNodeIdx ] = 1;
   return newNodeIdx;
}
template < typename node_t > U32  DedupMem< node_t >::Lookup  ( const node_t & node ) {

   // do a l/u
   #ifdef __USE_BIMAP__
   if( ddmMap.left.find( node ) == ddmMap.left.end() ) {
      return Alloc( node );
   }
   else {
      // inc rc
      const U32 plid = ddmMap.left.find( node )->second;
      IncRC( plid );
      return plid;
   }
   #else
   if( fwdMap.find( node ) == fwdMap.end() ) {
      return Alloc( node );
   }
   else {
      // inc rc
      const U32 plid = fwdMap.find( node )->second;
      IncRC( plid );
      return plid;
   }
   #endif
   assert( false );
   return 0;
}
template < typename node_t > U32  DedupMem< node_t >::Lookup  ( const node_t & node, const U32 lvl ) {

   // do a l/u
   #ifdef __USE_BIMAP__
   const bool alloc = ddmMap.left.find( node ) == ddmMap.left.end();
   #else
   const bool alloc = fwdMap.find( node ) == fwdMap.end();
   #endif
   
   vpceNodes[ lvl ] += 1;

   if( lvl && ( node.s[ deg-1 ] & 0x80000000 ) ) {
      U32 p = node.s[ deg-2 ];
      U32 d = 0;
      while( p > Log2Ceil( deg ) ) {
         virtNodes[ lvl-d ] += 1;
         // -- overcounts the uniqe path expanded nodes -- if( alloc ) {
         // -- overcounts the uniqe path expanded nodes --    upcxNodes[ lvl-d ] += 1;
         // -- overcounts the uniqe path expanded nodes -- }
         d++;
         p >>= Log2Ceil( deg );
      }
   }
   else {
      virtNodes[ lvl ] += 1;
      // -- overcounts the uniqe path expanded nodes -- if( alloc ) {
      // -- overcounts the uniqe path expanded nodes --    upcxNodes[ lvl ] += 1;
      // -- overcounts the uniqe path expanded nodes -- }
   }
   
   #ifdef __USE_BIMAP__
   if( alloc ) {
      uniqNodes[ lvl ] += 1;
      return Alloc( node );
   }
   else {
      // inc rc
      const U32 plid = ddmMap.left.find( node )->second;
      IncRC( plid );
      return plid;
   }
   #else
   if( alloc ) {
      uniqNodes[ lvl ] += 1;
      return Alloc( node );
   }
   else {
      // inc rc
      const U32 plid = fwdMap.find( node )->second;
      IncRC( plid );
      return plid;
   }
   #endif
   assert( false );
   return 0;
}
template < typename node_t > node_t DedupMem< node_t >::pread ( const U32 plid ) const {
   #ifdef __USE_BIMAP__
   return ddmMap.right.find( plid )->second;
   #else
   return bakMap.find( plid )->second;
   #endif
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
template class DedupMem< BNode >;
template class DedupMem< ONode >;
template class DedupMem< QNode >;
